The present invention relates to an image representation method using triangular mesh, and more particularly to a method for irregular triangular mesh representation of an image based on adaptive removal of control points defining the triangular mesh.
Recently, there have been increasing demands for video communication using very low bit-rates. In video coding at a low bit-rate, the proportion of motion information increases as the bit-rate is reduced. Consequently, efficient motion compensation is a key part of video coding is in very low bit-rate applications. The hybrid coding scheme based on block-based motion compensation and the discrete cosine transform (MC-DCT) has been most widely used. Though block-based motion compensation has provided relatively good overall performance, it also has several drawbacks including blocking artifacts due to the insufficiency of the motion model to represent the real object motion.
To overcome this limitation imposed by image processing based on blocks, several new approaches have been studied with regard to low bit-rate imaging such as MPEG-4. As a result of the studies, many coding methods employing more sophisticated motion models, such as image warping (or spatial transformation) have been proposed. These methods are shown in the following-references.
1! J. Nieweglowski, T. G. Campbell, and P. Haavisto, "A novel video coding scheme based on temporal prediction using digital image warping," IEEE Trans. Consumer Electronic, Vol. 39, pp. 141-150, Aug. 1993;
2! Y. Wang and 0. Lee, "Active mesh-a feature seeking and tracking image sequence representation scheme," IEEE Trans. Image Processing, Vol. 3, No. 5, pp. 610-624, Sept. 1994;
3! Y. Nakaya and H. Harashima, "Motion compensation based on spatial transformations," IEEE Trans. Circuit and Systems for video Technology, Vol. 4, No. 3, pp 339-356, June 1994;
4! G. J. Sullivan and R. L. Baker, "Motion compensation for video compression using control grid interpolation," Proc. ICASSP '91, Toronto, Canada, pp. 2713-2716, May 1991;
5! J. Nieweglowski and P. Haavisto, "Motion vector field reconstruction for predictive video sequence coding," International Workshop on Coding Technique for Very low Bit-Rate Video, United Kingdom, paper No. 6.4, Apr. 7-8, 1994.
6! Ouseb Lee and Yao Wang, "Non-uniform sampling and interpolation over deformed meshes and its hierarchical extension," Proc. SPIE Visual Communications and Image Processings '95, Vol. 2501, pp. 389-400, 1995.
In warping prediction, a set of control points are placed in an image frame and displacement for each control point is transmitted so that predicted frame can be reconstructed by using the spatial transformation of each control point. Two types of motion estimation, backward estimation and forward estimation are possible. In forward estimation, primary control points are placed in a previous frame and the motion is estimated by finding locations corresponding to a current frame. See Ref. 1!. In backward estimation, however, control points are defined in a current frame and their motion is referenced based on the previous frame. See Refs. 3!-5!. The forward estimation has advantages over the backward estimation because it is suitable for an irregular mesh structure without requiring additional information on the mesh structure. It has also been noted that the use of an irregular mesh structure can reduce the prediction error.
Irregular mesh generation algorithms have been well studied in the area of computer graphics to model solid three-dimensional objects. The following references are illustrative:
7! H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle, "Mesh optimization," Computer Graphics (SIGGRAPH'93 Proceedings), Anaheim, Calif., pp. 19-26, Aug. 1-6, 1993;
8! G. Turk, "Re-tiling polygonal surfaces," Computer Graphics (SIGGRAPH'92 Proceedings), Chicago, pp 55-64, Jul. 26-31, 1992;
9! W. J. Schroeder, J. A. Zarge, and W. E. Lorensen Decimation of Traingular meshes," Computer Graphics (SIGGRAPH '92 Proceedings), Chicago, pp 65-70, Jul. 26-31, 1992.
Recently, Wang and Lee proposed an image sequence representation scheme using non-uniform control points embedded in a deformed mesh structure where each frame is initially represented by regular rectangular meshes (or rectangular meshes generated using quad tree segmentation). See Refs. 2!-6!. The original regular meshes are deformed so that each control point is moved to the closest feature point, such as an edge. Wang et al. have shown that an irregular mesh can represent a frame more accurately than the uniform regular mesh. However, there is a problem of determining the valid positions of the control points in the regions having no salient features because the schemes of Wang and Lee use local feature tracking algorithms for a fixed number of control points based on the initial regular meshes.